package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href="https://www.nowcoder.com/practice/508378c0823c423baa723ce448cbfd0c?tpId=13&tqId=634&ru=%2Fpractice%2F7fe2212963db4790b57431d9ed259701&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=">二叉树中和为某一值的路径(一)</a>
 * <p>
 * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。<br>
 * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点<br>
 * 2.叶子节点是指没有子节点的节点<br>
 * 3.路径只能从父节点到子节点，不能从子节点到父节点<br>
 * 4.总节点数目为n<br>
 * </p>
 *
 * @author c2b
 * @since 2023/3/9 13:54
 */
public class JzOffer0082HasPathSum {

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum) {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    public boolean hasPathSum2(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode currNode = queue.poll();
            if (currNode.left == null && currNode.right == null && currNode.val == sum) {
                return true;
            }
            if (currNode.left != null) {
                currNode.left.val = currNode.left.val + currNode.val;
                queue.offer(currNode.left);
            }
            if (currNode.right != null) {
                currNode.right.val = currNode.right.val + currNode.val;
                queue.offer(currNode.right);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(1);
        root.right.right = new TreeNode(9);
        root.left.right = new TreeNode(11);
        root.left.right.left = new TreeNode(2);
        root.left.right.right = new TreeNode(7);

        //TreeNode root = new TreeNode(1);
        // root.left = new TreeNode(2);
        JzOffer0082HasPathSum jzOffer0082HasPathSum = new JzOffer0082HasPathSum();
        System.out.println(jzOffer0082HasPathSum.hasPathSum2(root, 22));
    }
}
